
#include<iostream>
#include<Vector>
#include<stack>

using namespace std;

class node
{
public :
	int val;
	node* left;
	node* right;
	node(int x)
		:val(x),
		left(nullptr),
		right(nullptr)
	{}
};

//非递归前序遍历
vector<int> preordered(node* root) 
{
	stack<node*>st;    
	vector<int>ret; 
	if (root)st.push(root);   //先将根节点压栈
	while (st.size())
	{
		//弹出并加到目标数组中
		auto root = st.top();
		st.pop();
		ret.push_back(root->val);  
		//因为要先处理左子树
		if (root->right)st.push(root->right);//先压右子树
		if (root->left)st.push(root->left);  //再压左子树
	}
	return ret;
}

//非递归后序遍历
vector<int> postordered(node* root) 
{
	stack<node*> st;   
	if (root)st.push(root);
	vector<int>ret;
	while (st.size())
	{
		auto root = st.top();
		st.pop();    
		ret.push_back(root->val);
		//后续翻转,所以先处理弹右子树,就是先压栈左子树,后压栈右子树
		if (root->left)st.push(root->left);
		if (root->right)st.push(root->right);
	}
	reverse(ret.begin(), ret.end()); 
	return ret;
}


//非递归中序遍历
vector<int> midordered(node* root)
{
	stack<node*>st;
	vector<int>ret;
	node* cur = root;
	while (cur || st.size())//?????
	{
		if (cur)
		{
			st.push(cur);  
			cur = cur->left;
		}
		else
		{
			auto root = st.top();
			st.pop();
			ret.push_back(root->val);   
			cur = root;//再访问右子树
			cur = cur->right;     
		}
	}
	return ret;
}

int main()
{
	node* n1 = new node(1);  
	node* n2 = new node(2);    
	node* n3 = new node(3);   
	node* n4 = new node(4);   
	node* n5 = new node(5);   
	node* n6 = new node(6);   

	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;
	n3->right = n6;
	stack <node*> st;    
	vector<int>ret;

	ret=preordered(n1);  
	cout << "非递归前序遍历为: " << endl; 
	for (auto x : ret)
		cout << x << " ";
	cout << endl; 
	ret = postordered(n1);
	cout << "非递归后序遍历为: " << endl; 
	for (auto x : ret)
		cout << x << " ";
	cout << endl;

	ret=midordered(n1);
	cout << "非递归中序遍历为: " << endl;
	for (auto x : ret)
		cout << x << " ";
	cout << endl;
	return 0;
}
